1. Field of the Invention
The present invention relates to an encryption technique for maintaining the security of information, and in particular relates to an encryption/decryption technique, a digital signature/verification technique, and a key agreement technique which use an elliptic curve.
2. Description of the Related Art
&lt;Public-Key Encryption&gt;
Data communication that uses computer and communication techniques has become pervasive in recent years. Secret communication or digital signature techniques are used in such data communication. Secret communication techniques allow communication to be performed without the communicated content being revealed to third parties. Digital signature techniques, meanwhile, enable a receiver to verify whether the communicated content is valid or whether the information is from the stated sender.
Such secret communication or digital signature techniques use a cryptosystem called public-key encryption. Public-key encryption provides a convenient method for managing the separate encryption keys of many users, and so has become a fundamental technique for performing communication with a large number of users. In secret communication based on public-key encryption, different keys are used for encryption and decryption, with the decryption key being kept secret and the encryption key being made public.
Here, one of the founding principles for the security of public-key encryption is the so-called "discrete logarithm problem". Representative examples of the discrete logarithm problem are problems defined over finite fields and problems based on elliptic curves. Such problems are described in detail in Neal Koblitz, A Course in Number Theory and Cryptography (Springer-Verlag, 1987).
&lt;Discrete Logarithm Problem based on Elliptic Curve&gt;
A discrete logarithm problem based on an elliptic curve is as follows.
E(GF(p)) is the elliptic curve E defined over the finite field GF(p), with an element G, given when the order of E is exactly divided by a large prime number, being set as a base point. This being so, the problem is to calculate an integer x that satisfies EQU Y=x*G (Formula 1)
where Y is a given element on the elliptic curve E and such an integer x actually exists.
Here, p is a prime number and GF(p) is a finite field that includes p elements. Note that in this specification the sign * represents exponentiation of an element included in an elliptic curve, so that x*G=G+G+ . . . +G where the element G is cumulated x times.
The reason a discrete logarithm problem assists in the security of public-key encryption is that the above calculation of x is extremely difficult for a large finite field GF(p).
&lt;ElGamal Signature Scheme Which Uses Discrete Logarithm Problem Based on Elliptic Curve&gt;
The following is a description of the ElGamal signature scheme which uses a discrete logarithm problem based on an elliptic curve.
FIG. 1 is a sequence diagram showing the digital signature procedure by the ElGamal signature scheme.
A user A 110, a management center 120 and a user B 130 are connected together via a network.
First, a prime number is set as p, an elliptic curve over a finite field GF(p) is set as E, a base point of E is set as G, and the order of E is set as q. Which is to say, q is the smallest positive integer that satisfies EQU q*G=0 (Formula 2)
Note that a point (.infin.,.infin.) whose x and y coordinates are both .infin. is called "point at infinity" and expressed as 0. When an elliptic curve is regarded as a group, 0 acts as "zero-element" in addition operations.
(1) Generation of Public Key by Management Center 120
Using a secret key xA given by the user A 110 beforehand, the management center 120 generates a public key YA for the user A 110 according to Formula 3 (steps S141-S142). EQU YA=XA*G (Formula 3)
The management center 120 then announces the prime number p, the elliptic curve E and the base point G as system parameters, and reveals the public key YA of the user A 110 to the user B 130 (steps S143-S144).
(2) Generation of Signature by User A 110
The user A 110 generates a random number k (step S145).
The user A 110 then calculates EQU R1=(rx,ry)=k*G (Formula 4)
(step S146), and finds s that satisfies EQU s.times.k=m+rx.times.xA(mod q) (Formula 5)
(step 147), where m denotes a message to be sent from the user A 110 to the user B 130.
The user A 110 sends (R1,s) as a signature to the user B 130 together with the message m (step S148).
(3) Verification of Signature by User B 130
The user B 130 verifies the validity of the user A 110 that is the sender of the message m, by judging whether Formula 6 is satisfied (step S149). EQU s*R1=m*G+rx*YA (Formula 6)
Here, Formula 6 derives from ##EQU1##
&lt;Computational Complexity of Addition and Doubling in Elliptic Curve Exponentiation&gt;
In the above ElGamal digital signature scheme which uses a discrete logarithm problem based on an elliptic curve, elliptic curve exponentiation is repeatedly performed to generate the public key and the signature and to verify the signature. For example, xA*G in Formula 3, k*G in Formula 4, s*R1, m*G and rx*YA in Formula 6 are such elliptic curve exponentiation. For details on elliptic curve exponentiation, see "Efficient Elliptic Curve Exponentiation" in Miyaji, Ono & Cohen, Advances in Cryptology-Proceedings of ICICS'97, Lecture Notes in Computer Science, pp.282-290 (Springer-Verlag, 1997).
Formulas used in elliptic curve exponentiation will be explained below.
Let EQU y 2=x 3+.alpha..times.x.beta.
be the equation of an elliptic curve. In this specification, the sign represents a repeated multiplication, so that 2 3=2.times.2.times.2.
Let P=(x1,y1) and Q=(x2,y2) be two arbitrary points on the elliptic curve and R=(x3,y3) be a point defined by R=P+Q.
When P.noteq.Q, R=P+Q is an addition operation using addition formulas that are EQU x3={(y2-y1)/(x2-x1)} 2-x1-x2 EQU y3={(y2-y1)/(x2-x1)}(x1-x3)-y1
When P=Q, on the other hand, R=P+Q=P+P=2.times.P, so that R=P+Q is a doubling operation using doubling formulas that are EQU x3={(3.times.1 2+.alpha.)/2y1}2-2.times.1 EQU y3={(3.times.1 2+.alpha.)/2y1}(x1-x3)-y1
Note that the above operations are performed on a finite field where the elliptic curve is defined.
As shown in the addition formulas, when performing the addition operation over the elliptic curve in the 2-tuple coordinates called affine coordinates, it is necessary to perform one division over the finite field. One division over a finite field requires an average of 10 times as much computational complexity as one multiplication over the finite field.
To reduce this computational complexity, 3-tuple coordinates called projective coordinates are used instead.
Projective coordinates are 3-tuple coordinates made up of X, Y, and Z, wherein if a number n and two points (X,Y,Z) and (X',Y',Z') satisfy the relationship EQU X'=nX, Y'=nY, Z'=nZ
then EQU (X,Y,Z)=(X',Y',Z')
Projective coordinates (X,Y,Z) correspond to affine coordinates (x,y) as follows: EQU (x,y).fwdarw.(x,y,1) EQU (X,Y,Z).fwdarw.(X/Y,Y/Z) (where Z.apprxeq.0)
Here, the sign .fwdarw. is used in such a way that S1.fwdarw.S2 when an element in a set S1 corresponds to an element in a set S2.
Hence the following description will be made on the premise that all computations over elliptic curves are performed in projective coordinates.
Addition and doubling formulas used for an elliptic curve in projective coordinates will be explained below. These formulas are consistent with the addition and doubling formulas in affine coordinates given above.
Elliptic curve exponentiation is achieved by repeating additions and doublings. Here, while computational complexity of an addition is unchanged regardless of parameters in an elliptic curve, computational complexity of a doubling is dependent on the parameters in the elliptic curve.
Let p be a 160-bit prime number and E: y 2=x 3+.alpha..times.x+.beta. be an elliptic curve over a finite field GF(p).
When elements P and Q on the elliptic curve E are set respectively as P=(X1,Y1,Z1) and Q=(X2,Y2,Z2), R=(X3,Y3,Z3)=P+Q is calculated as follows.
(1) Addition (where P.apprxeq.Q)
(1-1) Calculation of Intermediate Values
The following is calculated. EQU U1=X1.times.Z2 2 (Formula 8) EQU U2=X2.times.Z1 2 (Formula 9) EQU S1=Y1.times.Z2 3 (Formula 10) EQU S2=Y2.times.Z1 3 (Formula 11) EQU H=U2-U1 (Formula 12) EQU r=S2-S1 (Formula 13)
(1-2) Calculation of R=(X3,Y3,Z3)
The following is calculated. EQU X3=-H 3-2.times.U1.times.H 2+r 2 (Formula 14) EQU Y3=-S1.times.H 3+r.times.(U1.times.H 2-X3) (Formula 15) EQU Z3=Z1.times.Z2.times.H (Formula 16)
(2) Doubling (where P=Q (R=2P))
(2-1) Calculation of Intermediate Values
The following is calculated. EQU S=4.times.X1.times.Y1 2 (Formula 17) EQU M=3.times.X1 2+.alpha..times.Z1 4 (Formula 18) EQU T=-2.times.S+M 2 (Formula 19)
(2-2) Calculation of R=(X3,Y3,Z3)
The following is calculated. EQU X3=T (Formula 20) EQU Y3=-8.times.Y1 4+M.times.(S-T) (Formula 21) EQU Z3=2.times.Y1.times.Z1 (Formula 22)
Computational complexity when performing the above addition and doubling over the elliptic curve E can be estimated as follows. Here, computational complexity of one multiplication over the finite field GF(p) is measured as 1 Mul, while computational complexity of one squaring over the finite field GF(p) is measured as 1 Sq (1 Sq.apprxeq.0.8 Mul in general-purpose microprocessors).
Computational complexity of the addition over the elliptic curve E (where P.noteq.Q) is obtained by counting the number of multiplications and the number of squarings performed in Formulas 8-16. Since 1 Mul+1 Sq, 1 Mul+1 Sq, 2 Mul, 2 Mul, 2 Mul+2 Sq, 2 Mul, and 2 Mul are performed respectively in Formulas 8, 9, 10, 11, 14, 15, and 16, the computational complexity of the addition is 12 Mul+4 Sq.
Similarly, computational complexity of the doubling over the elliptic curve E (where P=Q) is obtained by counting the number of multiplications and the number of squarings performed in Formulas 17-22. Since 1 Mul+1 Sq, 1 Mul+3Sq, 1 Sq, 1 Mul+1 Sq, and 1 Mul are performed respectively in Formulas 17, 18, 19, 21, and 22, the computational complexity of the doubling is 4 Mul+6 Sq.
It should be noted that there are certain rules in counting the number of multiplications and the number of squarings. For instance, H 3 in Formula 14 can be expanded as H 3=H 2.times.H, so that computational complexity of H 3 is 1 Mul+1 Sq. In the same way, Z1 4 in Formula 18 can be expanded as Z1 4=(Z1 2) 2, so that computational complexity of Z1 4 is 2 Sq.
Also, H 2 in Formula 14 is not included in the number of squarings, since H 2 has already been calculated in the calculation of H 3 in the same formula.
Also, a multiplication of a given value by a small value is not included in the number of multiplications due to the following reason.
Small values noted here are small fixed values, such as 2, 3, 4, and 8, that are used for multiplications in Formulas 8-22. Such values can each be expressed in binary with 4 bits at the maximum, while the other parameters in the formulas are mostly 160 bits long.
In microprocessors, a multiplication of a multiplicand by a multiplier is normally achieved by repeatedly shifting the multiplicand and calculating the sum. More specifically, when a bit of a multiplier expressed in binary shows "1", a multiplicand expressed in binary is shifted to justify the least significant bit of the multiplicand to the position of the bit of the multiplier, thereby generating one bit string. After repeating the above shift for every bit of the multiplier, one or more bit strings are generated and totaled.
When a multiplier and a multiplicand are both 160 bits long, the 160-bit multiplicand is shifted 160 times, and as a result 160 bit strings are obtained and totaled. On the other hand, when a multiplier is 4 bits long and a multiplicand is 160 bits long, the 160-bit multiplicand is shifted 4 times, and as a result 4 bit strings are obtained and totaled.
Thus, in a multiplication of a given value by a small value, shift does not have to be repeated many times, so that computational complexity of the multiplication can be neglected. Accordingly, such a multiplication is not counted in the number of multiplications.
This rule can be applied to the following case. If a small value is assigned to the parameter a of the elliptic curve E in Formula 18 in the doubling operation, the computational complexity of the doubling can be reduced by 1 Mul to be 3Mul+6Sq. Meanwhile, the computational complexity of the addition operation is unchanged even if parameters of the elliptic curve are changed.
&lt;Selection of Elliptic Curve Suitable for Encryption&gt;
A method of selecting an elliptic curve suitable for use in encryption will be explained below. For details on the method, see IEEE P1363 Working Draft (IEEE, Feb. 6, 1997).
An elliptic curve suitable for encryption can be obtained by repeating the following steps.
(1) Selection of Arbitrary Elliptic Curve
First, two parameters on a finite field GF(p) are arbitrarily selected and set as .alpha. and .beta.. Here, .alpha. and .beta. satisfy EQU 4.times..alpha.3+27.times..beta.2.apprxeq.0 (mod p) (Formula 23)
and p denotes a prime number.
Next, .alpha. and .beta. are used to set an elliptic curve E that is EQU E: y 2=x 3+.alpha..times.x+.beta.
(2) Judgement on Whether Elliptic Curve E is Suitable for Encryption
The number of elements #E(GF(p)) in the elliptic curve E obtained in (1) is calculated, and the elliptic curve E is adopted when Conditions 1 and 2 are met.
(Condition 1) #E(GF(p)) is exactly divisible by a large prime number
(Condition 2) #E(GF(p))-(p+1).apprxeq.0, -1
When any of Conditions 1 and 2 is not met, the elliptic curve E is rejected and (1) and (2) are performed again where a new elliptic curve is arbitrarily selected and its suitability is judged.
&lt;Problems of Conventional Techniques&gt;
As described above, when a fixed small value is assigned to the parameter .alpha. of the elliptic curve, computational complexity of elliptic curve exponentiation can be reduced. However, it is difficult to select a secure elliptic curve that is suitable for use in encryption, since the value of the parameter .alpha. is fixed beforehand.
On the other hand, when the above selection method is used, a secure elliptic curve suitable for use in encryption can be selected. However, it is difficult to reduce computational complexity, since a small value may not necessarily assigned to the parameter .alpha. of the elliptic curve.
Thus, with the conventional techniques, it is impossible to select a secure elliptic curve suitable for encryption and at the same time reduce computational complexity for the elliptic curve, due to the above mutually contradictory problems.